/// @tags:
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

namespace BlueQuantum {

int constexpr N = 5e3 + 5;

int n, m;
int t[N], p[N], x[N], f[N][N];

inline void max(int &a, int b) { a < b && (a = b); }

inline int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> t[i];
  cin >> m;
  for (int i = 1; i <= m; ++i) {
    cin >> p[i] >> x[i];
  }
  for (int k = 1; k <= m; ++k) {
    memset(f, -0x3f, sizeof(f));
    int tmp = t[p[k]];
    t[p[k]] = x[k];
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j <= i; ++j) {
        if (j != 0) max(f[i][j], f[i - 1][j - 1] + j - t[i]);
        max(f[i][0], f[i - 1][j]);
      }
    }
    int ans = 0;
    for (int i = 0; i <= n; ++i) max(ans, f[n][i]);
    cout << ans << '\n';
    t[p[k]] = tmp;
  }
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("drink.in", "r", stdin);
  freopen("drink.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
